Postorder Traversal

Definition / 释义

后序遍历：一种树的遍历方式，通常按“先访问子节点，再访问父节点”的顺序进行；对二叉树而言，访问顺序一般是“左子树 → 右子树 → 根节点”。（该术语也常用于表达式树求值、删除树节点、语法树处理等场景。）

Pronunciation / 发音（IPA）

/ˌpoʊstˈɔːrdər ˈtrævərsəl/

Examples / 例句

We used postorder traversal to delete the tree safely.
我们用后序遍历来安全地删除这棵树。

In the compiler, the abstract syntax tree is often processed with a postorder traversal so that child expressions are evaluated before their parent nodes.
在编译器中，抽象语法树常用后序遍历来处理，这样可以先计算子表达式，再计算父节点。

Etymology / 词源

postorder 由 post-（“之后”）+ order（“顺序”）构成，字面意思是“在（某种）顺序之后”；在树遍历语境中，指把“根节点的访问”放在子树访问之后。traversal 源自 traverse（“穿越、遍历”），在计算机科学中固定指“按规则访问数据结构中的所有节点”。

Related Words / 相关词汇

• Inorder Traversal
• Preorder Traversal
• Depth-First Search
• Breadth-First Search
• Binary Tree
• Abstract Syntax Tree

Literary Works / 文献与作品中的用例

• Introduction to Algorithms（Cormen, Leiserson, Rivest, Stein，常称 CLRS）：在树与图的章节中讨论 DFS 及其与先序/后序处理的关系。
• Algorithms（Robert Sedgewick & Kevin Wayne）：在树与图的实现与遍历部分涉及后序处理（postorder）。
• The Art of Computer Programming（Donald E. Knuth）：在基础数据结构与树相关内容中讨论树遍历思想（包括与后序相对应的处理方式）。